/* 20240422：实现数据结构中顺序表的相关代码 */
#include <stdbool.h>
// 1.定义一个顺序表
// a.静态分配的顺序表
#define MaxSize 50// 定义顺序表的最大长度
typedef struct SequeceList_Static {
    int data[MaxSize];// 顺序表的元素
    int length;// 顺序表的实际长度
} SqList;
// b.动态分配的顺序表
#define initSize 100// 预定义初始化顺序表时的最大长度
typedef struct SequeceList_dynamic {
    int *data;// 指向动态分配数组的指针
    int maxSize, length;// 动态分配数组的最大容量和实际长度
} SeqList;
// 注：上面是动态分配数组的顺序表的定义，若要使用此数据结构，需进行动态分配内存
// C的初始化动态分配内存语句：SeqList.data=(int*)malloc(initSize*sizeof(int));
// C++的初始化动态分配内存语句：SeqList.data=new int[initSize];
/**
   顺序表（线性表）的基本操作：
•	InitList(&L)：初始化表。构造一个空的线性表。
•	Length (L)：求表长。返回线性表L的长度，即L中数据元素的个数。
•	LocateElem(L, e)：按值查找操作。在表L中查找具有给定关键字值的元素。
•	GetElem(L, i)：按位查找操作。获取表L中第i个位置的元素的值。
•	ListInsert(&L, i, e)：插入操作。在表L中的第i个位置上插入指定元素e，成功返回true，否则返回false。
•	ListDelete(&L, i, &e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。 
•   PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。 
•   Empty(L)：判空操作。若L为空表，则返回true，否则返回false。 
•   DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
注：1）&L是C++的引用用法，无需解引用，C要达到同样效果只能用指针；
    2）数据结构的基本操作是在算法中使用到此数据结构时可以直接调用的函数，一般函数名是固定的，调用时直接用上面的函数名，
    本次代码只是为了区分静态分配和动态分配的实现方式而分别命名，一般没有特殊说明，采用静态方式的方式实现。    
 */
// 2.顺序表的初始化
void InitList_Sq(SqList *sqList) {// 初始化静态分配的顺序表
    sqList->length = 0;
}
void InitList_Seq(SeqList *seqList) {// 初始化动态分配的顺序表
    // 动态分配顺序表与静态不同的地方在于动态表需要分配内存和初始化存储容量，而这些静态表在定义时就已经完成了
    seqList->data = (int *) malloc(initSize * sizeof(int));
    seqList->length = 0;
    seqList->maxSize = initSize;
}
// 3.Length (L)：求表长，这个表长度在结构体中已定义，直接访问即可，即L.length
// 4.LocateElem(L, e)：按值查找，在表L中查找具有给定关键字值的元素。
int LocateListElem_Sq(SqList L, int e) {// 静态顺序表
    // int sqData[] = L.data; // 获取顺序表数组，可直接访问，这一步省略
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;// 顺序表的位序 = 数组下标 + 1
        }
    }
    return 0;// 退出循环，查找失败
}
int LocateListElem_Seq(SeqList L, int e) {// 动态顺序表
    // int *seqData = L.data; // 获取顺序表数组，可直接访问，这一步省略
    for (int i = 0; i < L.length; i++) {
        if (*(L.data + i) == e) {
            return i + 1;// 顺序表的位序 = 数组下标 + 1
        }
    }
    return 0;// 退出循环，查找失败
}
// 5.GetElem(L, i)：按位查找，获取表L中第i(1<=i<=L.length+1)个位置的元素的值。
int GetListElem_Sq(SqList L, int i) {// 静态顺序表
    return L.data[i - 1];
}
int GetListElem_Seq(SeqList L, int i) {// 静态顺序表
    return *(L.data + (i - 1));
}
// 6.ListInsert(&L, i, e)：插入操作，在表L中的第i个位置上插入指定元素e。
bool ListInsert_Sq(SqList *sqList, int i, int e) {// 静态顺序表
    // 插入前需检查i的合法性，其实上面带i的参数也应检查
    if (i < 1 || i > sqList->length + 1) {// 判断i的范围是否有效
        return false;
    }
    if (sqList->length > MaxSize) {// 当前存储空间已满，不能插入
        return false;
    }
    for (int j = sqList->length; j >= i; j--) {// 将第i个元素及之后的元素后移
        sqList->data[j] = sqList->data[j - 1];
    }
    sqList->data[i - 1] = e;
    sqList->length++;
    return true;
}
// 注：动态顺序表和静态顺序表在于访问数据元素的方式不同，其他一样，后面不再展示
bool ListInsert_Seq(SeqList *seqList, int i, int e) {
    if (i < 1 || i > seqList->length + 1) {// 判断i的范围是否有效
        return false;
    }
    if (seqList->length > MaxSize) {// 当前存储空间已满，不能插入
        return false;
    }
    for (int j = seqList->length; j >= i; j--) {
        *(seqList->data + j) = *(seqList->data + (j - 1));
    }
    *(seqList->data + (i - 1)) = e;
    seqList->length - 1;
}
// 7.ListDelete(&L, i, &e)：删除操作，删除表L中第i(1<=i<=L.length)个位置的元素，并用e返回删除元素的值。
bool ListDelete_Sq(SqList *sqList, int i, int e) {
    if (i < 1 || i > sqList->length + 1) {// 判断i的范围是否有效
        return false;
    }
    e = sqList->data[i - 1];// 将被删除元素赋值给返回给e
    for (int j = i; j < sqList->length; j++) {// 将第i个位置后的元素前移
        sqList->data[j - 1] = sqList->data[j];
    }
    sqList->length--;
    return true;
}
// 8.PrintList(L)：输出操作，按前后顺序输出线性表L的所有元素值。（遍历）
int PrintList_Sq(SqList sqList) {
    for (int i = 0; i < sqList.length; i++) {
        printf("当前顺序表的元素：\n{%d\t}", sqList.data[i]);
    }
    return 0;
}
// 9.Empty(L)：判空操作，若L为空表，则返回true，否则返回false。
bool EmptyList_Sq(SeqList sqList) {
    return sqList.length == 0;
}
// 10.DestroyList(&L)：销毁操作，销毁线性表，并释放线性表L所占用的内存空间。
// 验证
int main() {
    return 0;
}
